#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cmath> // for pow
#include <set>

// 为了方便展示，将所有函数都放在同一个文件内。
// 在实际开发中，可将它们拆分到多个文件中。

using namespace std;

/**
 * 存储路径信息的结构体
 */
struct Path {
    vector<size_t> nodes;  // 路径上的节点序列
    size_t length;         // 路径总长度

    // 使得优先队列按照 length 的升序来取最小值
    bool operator>(const Path& other) const {
        return length > other.length;
    }
};

/**
 * Dijkstra 算法：找到从起点 start 到终点 end 的最短路径（节点序列）
 * @param start 起点
 * @param end   终点
 * @param roadlength 邻接矩阵，roadlength[u][v] = 从 u 到 v 的边长（或无穷大表示不可达）
 * @return 若能找到最短路径，返回节点序列；否则返回空
 */
vector<size_t> dijkstra(size_t start, size_t end, const vector<vector<size_t>>& roadlength) {
    const size_t INF = INT_MAX;
    const size_t n = roadlength.size();
    vector<size_t> dist(n, INF);
    dist[start] = 0;
    vector<size_t> prev(n, INF);

    // 小根堆：pair 的 first 表示当前距离，second 表示顶点编号
    priority_queue<pair<size_t, size_t>, vector<pair<size_t, size_t>>, greater<pair<size_t, size_t>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (u == end) {
            break;  // 找到了最短路径
        }
        if (d > dist[u]) {
            continue;  // 已有更优距离
        }

        for (size_t v = 0; v < n; ++v) {
            if (roadlength[u][v] != INF && dist[v] > dist[u] + roadlength[u][v]) {
                dist[v] = dist[u] + roadlength[u][v];
                prev[v] = u;
                pq.push({dist[v], v});
            }
        }
    }

    // 如果无法到达 end，dist[end] 依然是 INF
    if (dist[end] == INF) {
        return {};
    }

    // 回溯 prev 数组，得到路径
    vector<size_t> path;
    for (size_t cur = end; cur != start; cur = prev[cur]) {
        if (prev[cur] == INF) {
            // 理论上不会出现，但以防万一
            return {};
        }
        path.push_back(cur);
    }
    path.push_back(start);

    // 反转即为从 start -> end 的路径
    reverse(path.begin(), path.end());
    return path;
}

/**
 * 计算路径在原始图中的总长度
 * @param path 路径的节点序列
 * @param roadlength 邻接矩阵
 * @return 路径的总长度
 */
size_t calculatePathLength(const vector<size_t>& path, const vector<vector<size_t>>& roadlength) {
    size_t length = 0;
    for (size_t i = 0; i < path.size() - 1; ++i) {
        length += roadlength[path[i]][path[i + 1]];
    }
    return length;
}

/**
 * Yen's Algorithm：找到从 start 到 end 的前 k 条不同最短路径
 * 
 * 如果要严格按照论文里处理，需要更复杂的“截断-恢复”逻辑。
 * 这里演示一种简化写法，但加了去重机制，避免陷入死循环。
 *
 * @param start 起点
 * @param end   终点
 * @param k     需要的最短路径条数
 * @param roadlength 邻接矩阵
 * @return 返回最多 k 条不同的最短路径（节点序列）
 */
vector<vector<size_t>> yen_ksp(size_t start, size_t end, size_t k, const vector<vector<size_t>>& roadlength) {
    // 用于存储最终的最短路径集合（结果）
    vector<vector<size_t>> P;
    if (k == 0) {
        return P;
    }

    // 1. 先找到第一条最短路径
    auto firstPath = dijkstra(start, end, roadlength);
    if (firstPath.empty()) {
        // 不存在任何路径
        return P;
    }
    P.push_back(firstPath);

    // 优先队列，按照路径长度升序
    priority_queue<Path, vector<Path>, greater<Path>> Q;

    // 为了避免无限生成重复或等效路径，维护一个“已生成”的路径集合
    // 注意这里比较严格，只有完全相同的节点序列才视为重复
    // 如果想更严格防止陷入循环，可以把“包含环的路径”直接丢弃等
    set<vector<size_t>> usedPaths;
    usedPaths.insert(firstPath);

    // 2. 针对第一条最短路径，每个节点都尝试做“偏离”
    size_t baseLen = calculatePathLength(firstPath, roadlength);
    for (size_t i = 0; i < firstPath.size() - 1; ++i) {
        // 要禁用的边是 (r, s)
        size_t r = firstPath[i];
        size_t s = firstPath[i + 1];

        vector<vector<size_t>> modified_roadlength = roadlength;
        // 禁止使用这条边
        modified_roadlength[r][s] = INT_MAX;
        modified_roadlength[s][r] = INT_MAX;

        // 从 r 到 end 的最短路径
        auto spurPath = dijkstra(r, end, modified_roadlength);
        if (!spurPath.empty()) {
            // 将 [firstPath 的前 i+1 个节点] 与 spurPath（除去重复的 r）拼接
            vector<size_t> newPath(firstPath.begin(), firstPath.begin() + i + 1);
            // spurPath 第一个节点就是 r，所以要避开重复添加
            newPath.insert(newPath.end(), spurPath.begin() + 1, spurPath.end());

            // 计算该新路径在原图中的长度
            size_t newLen = calculatePathLength(newPath, roadlength);

            // 如果没出现过，就放入候选
            if (!usedPaths.count(newPath)) {
                usedPaths.insert(newPath);
                Q.push({newPath, newLen});
            }
        }
    }

    // 3. 不断从 Q 中取出最短候选路径，加入结果 P，并对它再次做类似的偏离操作
    while (!Q.empty() && P.size() < k) {
        Path candidate = Q.top();
        Q.pop();

        // 再次检查一下，是否已经在 P 里
        // （可能因为并发或其他原因重复；当然此处单线程逻辑意义不大，保险起见）
        bool duplicate = false;
        for (auto &p : P) {
            if (p == candidate.nodes) {
                duplicate = true;
                break;
            }
        }
        if (duplicate) {
            continue; 
        }

        // 放入结果
        P.push_back(candidate.nodes);

        // 依然要对该路径做偏离
        for (size_t i = 0; i < candidate.nodes.size() - 1; ++i) {
            size_t r = candidate.nodes[i];
            size_t s = candidate.nodes[i + 1];

            vector<vector<size_t>> modified_roadlength = roadlength;
            modified_roadlength[r][s] = INT_MAX;
            modified_roadlength[s][r] = INT_MAX;

            auto spurPath = dijkstra(r, end, modified_roadlength);
            if (!spurPath.empty()) {
                // 组合新路径
                vector<size_t> newPath(candidate.nodes.begin(), candidate.nodes.begin() + i + 1);
                newPath.insert(newPath.end(), spurPath.begin() + 1, spurPath.end());
                size_t newLen = calculatePathLength(newPath, roadlength);

                // 如果这个新路径没出现过，加入候选
                if (!usedPaths.count(newPath)) {
                    usedPaths.insert(newPath);
                    Q.push({newPath, newLen});
                }
            }
        }
    }

    return P;
}

/**
 * 下面是“检测是否会发生堵车”的辅助结构和函数
 */
struct Event {
    size_t time;  // 事件发生的时刻
    size_t u;     // 起始节点
    size_t v;     // 结束节点
    bool enter;   // true 表示车辆进入(u->v)，false 表示车辆离开(u->v)

    // 使优先队列按照 time 的升序排列
    bool operator>(const Event& other) const {
        return time > other.time;
    }
};

/**
 * 检查当前车辆组合是否会导致堵车
 * @param combination 当前所有车辆选定的路径组合（M 个路径）
 * @param roadlength  邻接矩阵
 * @param restrictions 每条道路的流量限制 restrictions[u][v]
 * @return true 表示不堵车，false 表示会堵车
 */
bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    // 创建时间事件队列
    priority_queue<Event, vector<Event>, greater<Event>> eventQueue;

    // 将每辆车的行驶过程，转化为进入/离开事件
    for (const auto& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];

            // 车辆在 current_time 时刻进入 (u->v)
            eventQueue.push({current_time, u, v, true});
            // 车辆在 current_time + length 时刻离开 (u->v)
            eventQueue.push({current_time + length, u, v, false});

            current_time += length;
        }
    }

    // current_flow[u][v] 表示当前有多少车正在 (u->v) 这条边上
    vector<vector<size_t>> current_flow(roadlength.size(), vector<size_t>(roadlength.size(), 0));

    // 依时间顺序处理事件
    while (!eventQueue.empty()) {
        size_t current_time = eventQueue.top().time;

        // 收集所有“同一时刻”的事件
        vector<Event> sameTimeEvents;
        while (!eventQueue.empty() && eventQueue.top().time == current_time) {
            sameTimeEvents.push_back(eventQueue.top());
            eventQueue.pop();
        }

        // 先处理“离开”事件，释放车流量
        for (auto &event : sameTimeEvents) {
            if (!event.enter) {  // 离开
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }

        // 再处理“进入”事件，增加车流量
        for (auto &event : sameTimeEvents) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    // 超过限制，发生堵车
                    return false;
                }
            }
        }
    }

    // 如果所有事件都处理完，没有出现超限情况，则不堵车
    return true;
}

/**
 * 计算当前组合的总路径长度
 */
size_t calculateTotalLength(const vector<vector<size_t>>& combination,
                            const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const auto &path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}

/**
 * 回溯：遍历所有车辆路径组合
 * @param all_cars_paths 每辆车可选的候选路径列表 (M 个车，每个有若干条候选路径)
 * @param car_index 当前正在处理第几辆车
 * @param current_combination 当前已选的车的路径
 * @param roadlength 邻接矩阵
 * @param restrictions 流量限制
 * @param best_combination 存储最优（不堵车且总距离最短）的组合
 * @param min_total_length 记录当前最小的总路径长度
 */
void traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths,
                          size_t car_index,
                          vector<vector<size_t>>& current_combination,
                          const vector<vector<size_t>>& roadlength,
                          const vector<vector<size_t>>& restrictions,
                          vector<vector<size_t>>& best_combination,
                          size_t& min_total_length) {
    // 如果已经处理完所有车辆，检查是否是更优组合
    if (car_index == all_cars_paths.size()) {
        // 检查是否会堵车
        if (checkTraffic(current_combination, roadlength, restrictions)) {
            size_t total_length = calculateTotalLength(current_combination, roadlength);
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = current_combination;
            }
        }
        return;
    }

    // 逐一尝试当前车辆的所有候选路径
    for (const auto &path : all_cars_paths[car_index]) {
        current_combination.push_back(path);
        // 递归处理下一辆车
        traverseCombinations(all_cars_paths, car_index + 1, current_combination,
                             roadlength, restrictions, best_combination,
                             min_total_length);
        // 回溯
        current_combination.pop_back();
    }
}

/**
 * 最终：找到不堵车且总路径长度最短的组合
 */
void findBestCombination(const vector<vector<vector<size_t>>>& all_cars_paths,
                         const vector<vector<size_t>>& roadlength,
                         const vector<vector<size_t>>& restrictions) {
    vector<vector<size_t>> best_combination;
    size_t min_total_length = INT_MAX;

    // 回溯遍历所有组合
    vector<vector<size_t>> current_combination;
    traverseCombinations(all_cars_paths, 0, current_combination,
                         roadlength, restrictions, best_combination,
                         min_total_length);

    // 输出最优解
    if (!best_combination.empty()) {
        cout << "Best combination (total length: " << min_total_length << "):\n";
        for (size_t i = 0; i < best_combination.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination[i]) {
                // 节点索引转为 1-based 输出
                cout << node + 1 << " ";
            }
            cout << "\n";
        }
    } else {
        cout << "No valid combination found!\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    size_t N, M;
    cin >> N >> M;

    // 读入邻接矩阵 roadlength
    vector<vector<size_t>> roadlength(N, vector<size_t>(N, INT_MAX));
    // 读入每条边的流量限制 restrictions
    vector<vector<size_t>> restrictions(N, vector<size_t>(N, 0));
    // 读入每辆车的起终点
    vector<vector<size_t>> cars(M, vector<size_t>(2));

    // 读取道路长度矩阵
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> roadlength[i][j];
            // 若输入为 0 且非对角线，则视为不可达
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX;
            }
        }
    }

    // 读取道路流量限制矩阵
    for (size_t i = 0; i < N; ++i) {
        for (size_t j = 0; j < N; ++j) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点/终点
    for (size_t i = 0; i < M; ++i) {
        cin >> cars[i][0] >> cars[i][1];
        // 转成 0-based
        cars[i][0]--;
        cars[i][1]--;
    }

    // ========== 关键：为每辆车计算前 k 条最短路径 ==========
    // 可以根据需要手动指定一个合理的 k，防止过大
    // 例如让用户输入 k，或者固定一个安全上限等
    size_t k = (size_t)pow(SIZE_MAX, 1.0 / M);

    vector<vector<vector<size_t>>> all_cars_paths(M);

    // 给每辆车找出它的 k 条候选路径
    for (size_t i = 0; i < M; ++i) {
        size_t start = cars[i][0];
        size_t end = cars[i][1];

        // 使用修正后的 Yen’s KSP
        auto paths = yen_ksp(start, end, k, roadlength);

        // 如果 paths 为空，表示车 i 无法到达
        if (paths.empty()) {
            cerr << "Warning: Car " << i+1 << " cannot reach its destination!\n";
        }

        all_cars_paths[i] = paths;
    }

    // 遍历所有车辆的路径组合，找出总长度最短且不堵车的组合
    findBestCombination(all_cars_paths, roadlength, restrictions);

    return 0;
}